package algorithm.leetcode.medium;

/*
 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
 */

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/11/6
 */
public class Question46 {

    public static void main(String[] args) {
        Question46 question = new Question46();
        int[] nums = {1,2,3};
        List<List<Integer>> subsets = question.permute(nums);
        System.out.println(subsets);
    }

    public List<List<Integer>> permute(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new ArrayList<>(0);
        }
        List<List<Integer>> res = new ArrayList<>(10);
        LinkedList<Integer> queue = new LinkedList<>();
        for (int n : nums) {
            queue.offer(n);
        }
        dfs(res, queue, new LinkedList<>());
        return res;
    }

    private void dfs(List<List<Integer>> res, LinkedList<Integer> queue, LinkedList<Integer> arr) {
        if (queue.isEmpty()) {
            // 如果队列为空，则所有的元素都放入列表(栈)中了，将列表保存到结果集中
            res.add(new LinkedList<>(arr));
            return;
        }
        int size = queue.size();
        // 从队列中取出第一个元素，放入列表(栈)中，并继续下一层递归
        // 等下一层递归返回后，将列表(栈)中的元素弹出，放回到队列中
        for (int i = 0; i < size; i++) {
            arr.add(queue.poll());
            dfs(res, queue, arr);
            queue.offer(arr.removeLast());
        }

    }
}
